// m

// 数组intervals表示若干个区间的集合，请合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需要恰好原数组的所有区间

// 思路
// 设定一个数组ans，用于表示最终不重叠的区间数组，首先对原始区间按照区间左端点大小从小到大进行排序
// 先将第一个区间加入ans数组中，然后依次考虑后边的区间
// 如果第i个区间左端点在前一个区间右端点右侧，则这两个区间不会重合，直接将该区间加入ans数组中，否则的话，这两个区间重合，判断两个区间的右区间值
// 更新前一个区间的右区间值为较大值，然后继续考虑下一个区间

// 时间复杂度：O(nlogn)
// 空间复杂度：O(logn)
function merge(intervals) {
    intervals.sort((a, b) => a[0] - b[0])
    let ans = [intervals[0]]
    for (let i = 1; i < intervals.length; i++) {
        if (ans[ans.length - 1][1] < intervals[i][0]) {
            ans.push(intervals[i])
        } else {
            ans[ans.length - 1][1] = Math.max(ans[ans.length - 1][1], intervals[i][1])
        }
    }
    return ans
}

let intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
console.log(merge(intervals))